package insertionSort

import (
	mySort "algorithms/interface/sort"
	"golang.org/x/exp/constraints"
	"sort"
)

/*插入排序：每次将无序部分arr[i:n]的头元素arr[i]，插入到有序部分arr[0:i]的合适位置arr[j]中
  特性：对于有序的或近乎有序的数组，间复杂度会变为O(n)
*/

// Sort 插入排序法
// 顺序排序，从小到大
func Sort[E mySort.Comparable[E]](arr []E) {
	//arr[0:i]是有序的，arr[i:n]是无序的
	//循环不变量，未排序部分
	for i := 0; i < len(arr); i++ {
		j := i
		t := arr[i]
		//将 arr[i] 插入到合适的位置
		for ; j-1 >= 0 && t.CompareTo(arr[j-1]) < 0; j-- {
			arr[j] = arr[j-1]
		}
		arr[j] = t
	}
}

// Sort0 插入排序法
// 顺序排序，从小到大
// 需实现sort.Interface接口，才能进行排序
func Sort0[E sort.Interface](arr E) {
	//arr[0:i]是有序的，arr[i:n]是无序的
	//循环不变量，未排序部分
	for i := 0; i < arr.Len(); i++ {
		//将 arr[i] 插入到合适的位置

		//for j := i; j-1 >= 0; j-- {
		//	if arr.Less(j, j-1) {
		//		arr.Swap(j, j-1)
		//	} else {
		//		break
		//	}
		//}

		for j := i; j-1 >= 0 && arr.Less(j, j-1); j-- {
			arr.Swap(j, j-1)
		}
	}
}

// Sort3 插入排序法
// 顺序排序，从小到大
// 仅支持基础类型排序
func Sort3[E constraints.Ordered](arr []E) {
	//arr[0:i]是有序的，arr[n:i]是无序的
	//循环不变量，未排序部分
	for i := 0; i < len(arr); i++ {
		//将 arr[i] 插入到合适的位置
		for j := i; j-1 >= 0; j-- {
			if arr[j] < arr[j-1] {
				swap(arr, j, j-1)
			} else {
				break
			}
		}
	}
}

// Sort1 插入排序法 常数级别性能优化
// 顺序排序，从小到大
// 仅支持基础类型排序
func Sort1[E constraints.Ordered](arr []E) {
	//arr[0:i]是有序的，arr[i:n]是无序的
	//循环不变量，未排序部分
	for i := 0; i < len(arr); i++ {
		//将 arr[i] 插入到合适的位置
		j := i
		t := arr[i]
		//将swap三步操作变为一次赋值操作
		for ; j-1 >= 0 && t < arr[j-1]; j-- {
			arr[j] = arr[j-1]
		}
		arr[j] = t
	}
}

// Sort2 插入排序法 常数级别性能优化
// 顺序排序，从小到大
// 仅支持基础类型排序
func Sort2[E constraints.Ordered](arr []E) {
	//arr[i:n]是有序的，arr[0:i]是无序的
	//循环不变量，未排序部分
	for i := len(arr) - 1; i >= 0; i-- {
		j := i
		t := arr[i]
		for ; j+1 < len(arr) && t > arr[j+1]; j++ {
			arr[j] = arr[j+1]
		}
		arr[j] = t
	}
}

func swap[E any](arr []E, i, j int) {
	tem := arr[i]
	arr[i] = arr[j]
	arr[j] = tem
}
